// BTreeLevelOrderTraversal.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <queue>
using namespace std;
/*
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]


*/
// Definition for binary tree
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<vector<int> > levelOrder(TreeNode *root) 
{
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

	vector<vector<int> > rets;
	if(NULL == root)
	{
		return rets;
	}
	queue<TreeNode*> q;
	q.push(root);
	vector<int> level;
	
	TreeNode seperateFlag(INT_MAX);

	int nNodeinCurLevel =1;
	int nNodeinNextLevel = 0;
	while(!q.empty())
	{
		TreeNode* pNode = q.front();
		q.pop();
		nNodeinCurLevel --;	
		level.push_back(pNode->val);
		if(pNode->left)
		{
			q.push(pNode->left);
			nNodeinNextLevel ++;	
		}
		if(pNode->right)
		{
			q.push(pNode->right);
			nNodeinNextLevel++;
		}
		if(nNodeinCurLevel == 0)
		{
			rets.push_back(level);
			level.clear();
			nNodeinCurLevel = nNodeinNextLevel;
			nNodeinNextLevel = 0;
		}
		
		
		
	}

	return rets;
}


//approach2
 void LevelOrder_approach2(vector<vector<int> > &rlt, TreeNode * root, int level)
{
    if(root)
    {
        if(level >= rlt.size())
        {
            vector<int> row;
            row.push_back(root->val);
            rlt.push_back(row);
        }
        else
        {
                rlt[level].push_back(root->val);
        }
        LevelOrder_approach2(rlt, root->left, ++level);
        LevelOrder_approach2(rlt, root->right, level);
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

